package NowCoder.Mathematics;

/**
 * JZ65 不用加减乘除做加法
 * 简单  通过率：45.68%  时间限制：1秒  空间限制：64M
 * 知识点 基础数学
 * 描述
 * 写一个函数，求两个整数之和，要求在函数体内不得使用+、-、*、/四则运算符号。
 *
 * 数据范围：两个数都满足 −10≤n≤1000
 * 进阶：空间复杂度 O(1)，时间复杂度 O(1)
 *
 * 示例1
 * 输入：
 * 1,2
 * 返回值：
 * 3
 *
 * 示例2
 * 输入：
 * 0,0
 * 返回值：
 * 0
 *
 * https://www.nowcoder.com/practice/59ac416b4b944300b617d4f7f111b215?tpId=13&tqId=11201&ru=/exam/oj
 */
public class 不用加减乘除做加法_JZ65 {
    //TODO:请使用两种方法重写该题
    /** 非递归写法
     * 我们先来看一道非常简单的题，在计算机中数字是由二进制位表示的，
     * 也就是说是由0和1组成的，如果我们要实现0和1之间的加法该怎么实现呢，他会有4种组合方式
     *
     * 1，0+0=00
     * 2，0+1=01
     * 3，1+0=01
     * 4，1+1=10
     *
     * 我们发现一个很重要的规律，就是只有1+1有进位，其他的都没进位。
     * 所以我们判断有没有进位只需要判断a&b是否等于1即可，而a+b的值（不考虑进位）只需要计算a|b即可，看明白了这点，代码就呼之欲出了
     */
    public int Add(int num1,int num2) {
        int c = (num1 & num2) << 1;//进位的值
        int d = num1 ^ num2;//不考虑进位，相加的值
        return c | d;//或者 return c ^ d;
    }

    /**     递归写法
     * 1，我们看到如果不考虑进位，那么a+b的结果其实就是a^b的结果，我们该怎么把进位问题也考虑在内呢，
     *      实际上只有1+1的时候才会出现进位，1+0或者0+0都不会出现进位，所以我们首先想到的是&运算
     * 2，这里我们计算一下a&b的结果是1001，我们知道当&运算的结果为1的时候，说明参与&运算的两个都是1，
     *      既然两个都是1，那么相加的时候就肯定会有进位，所以他们进位的值实际上是10010（（a&b）<<1），
     *      然后在和0100相加就是我们要求的结果，10010+00100=10110，10110实际上就是22，也就是13+9的结果
     * 3，但我们好像忽略了一个问题，就是这道题要求不能使用加减乘除符号，而上面我们分析的时候使用了加号，
     *      所以明显不行。通过上面的分析实际上我们已经发现了一个规律，就是a+b通过^和&运算之后又再执行相加操作，
     *      所以我们首先想到的是递归，我们来看下代码
     */
    public int Add1(int num1, int num2) {
        if (num1 == 0 || num2 == 0)
            return  num1 ^ num2;
        return Add1(num1 ^ num2, (num1 & num2) << 1);
    }
}
